The need for stronger cryptography to secure computer-enabled communication is ever increasing. Security standards for public key cryptosystems are periodically heightened. Likewise, the need for exceptional security between users and certification authorities is growing due to the vulnerability of certification authorities to malicious interference from adversaries. These security considerations have implications for pairing-based cryptosystems, such as those that use properties of elliptic curves in an essential manner. As the heightened standards “up the ante” for the amount of security to be provided by existing systems, pairing-based cryptosystems should include some techniques that can provide exceptional security.
For introductory purposes, several concepts will now be briefly summarized. Public key cryptography is a form of cryptography that allows users to communicate securely without having prior access to a shared secret key. This is accomplished by using a pair of cryptographic keys, designated as public key and private key, related mathematically. The private key is kept secret, while the public key may be widely distributed. The public key encrypts data in a manner that only the private key of the pair can decrypt. Ideally, it is infeasible to deduce the private key of a pair from the public key.
Elliptic curve cryptography (ECC) is an approach to public-key cryptography based on the mathematics of elliptic curves, for example, on a property of elliptic curves that two points on a curve can be “added” to obtain a third point on the curve. ECC can enable using smaller keys than other techniques while providing comparable security. ECC can also enable bilinear mapping between groups based on pairings, such as Weil pairings or Tate pairings.
A “pairing,” as used herein, is a cryptographic primitive that can be defined as a bilinear, non-degenerate, efficiently computable mapping over certain groups. Thus, with respect to ECC, a pairing can be a function that takes as input two points on an elliptic curve and outputs an element of some multiplicative abelian group. Furthermore, a pairing satisfies some special properties, including the abovementioned bilinearity. Because they possess these properties, pairings are relatively difficult to construct. Two pairings presently used in cryptography are the abovementioned Weil pairing and Tate pairing.
A pairing can map pairs of elements of mathematical groups, such as groups G1 and G2, to elements of a third group, such as group G3. With respect to the bilinear property: for elements P and Q from G1 and G2, respectively, and for numbers a and b, if a pairing maps (P, Q) to an element R from G3 then it maps (aP, bQ) to an element abR; for elements P and R from G1 and Q from G2 it maps (P+R,Q) to the product of the values for (P,Q) and (R,Q). It should be noted that pairing operations were first implemented on elliptic curve groups, allowing construction of some new cryptographic primitives, such as Identity-Based Encryption and Short Digital Signature schemata. Presently, pairings are an important building block for numerous cryptographic protocols.
A Weil pairing, for example, can be defined as a construction of roots of unity via operations on an elliptic curve to create a bilinear pairing on a torsion subgroup of the elliptic curve. Thus, for a fixed natural number m, the Weil pairing em is a bilinear map that takes as input two m-torsion points on the elliptic curve, and outputs an m th root of unity. In particular, if the elliptic curve is defined over a finite field then the Weil pairing em outputs an m th root of unity over that finite field.
The Decisional Diffie-Hellman (DDH) problem is based on the assumption that a certain computational problem within a cyclic group is hard. In a cyclic group G of order q, the DDH assumption states that, given (g, ga, gb) for a randomly chosen generator g (and random a,bε{0, . . . , q−1}), the value gab appears at first glance to be a perfectly random element of G. This can be stated more formally by saying that (g, ga, gb, gab)—this input is called a “DDH triplet”—is indistinguishable from (g, ga, gb, gc) (where c is also chosen at random from {0, . . . , q−1}). Thus, solving the DDH problem can be used for deciding if three elements of a given group constitute a valid Diffie-Hellman triplet.
If G and G′ are two groups, with G written additively and G′ written multiplicatively, then the DDH problem, given P, aP, bP, and cP in G, becomes deciding whether c=ab (modulo the order of P). If there exists a bilinear, non-degenerate map (a pairing) “e” where e: G×G→G′, then one can efficiently solve the DDH problem in G, since c=ab if and only if e(aP, bP)=e(P, cP).
Likewise, solving the DDH problem can be applied with respect to two additive groups G1 and G2, instead of a single group G, using a pairing e: G1×G2→G′. Given P and aP in G1 and given Q and bQ in G2, where P and Q are of the same order r, the DDH problem becomes deciding whether a=b (mod r). The security of pairing-based cryptosystems is generally based on the intractability (without a map or pairing in hand) of some version of the Diffie-Hellman problem in some group G or in a pair of groups G1 and G2. As introduced above, the most popular pairing choices are Weil pairing and Tate pairing, both computable by a technique known as Miller's algorithm. The Tate pairing is considered by some to be more easily used in practical applications than the Weil pairing.